回溯法原理
回溯法也称试探法,它的基本思想是:从问题的某一种状态(初始状态)出发,搜索从这种状态出发所能达到的所有“状态”,当一条路走到“尽头”的时候(不能再前进),再后退一步或若干步,从另一种可能“状态”出发,继续搜索,直到所有的“路径”(状态)都试探过。这种不断“前进”、不断“回溯”寻找解的方法,就称作“回溯法”。
1.没回溯的匹配
/ab{1,3}c/ 匹配 abbbc
一次性到位,没有回溯
2.有回溯的匹配
- 实例1
/ab{1,3}c/ 匹配 abbc
匹配第三个b的时候,文本为c,回退上一个状态,不再匹配B,而是匹配洗下一个正则符号C
- 实例2
/".*"/ 匹配 "acd"ef
匹配过程: 匹配完第一个双引号,开始通配符匹配。 通配符匹配到f,然后发现没有第二个双引号。开始状态回退两步,发现可以匹配第二个双引号,然后结束。
怎么改?
3.常见回溯形式
贪婪量词
b{1,3}
惰性量词
虽然惰性量词不贪,但也会有回溯的现象
var string = "12345"; var regex = /^(\d{1,3}?)(\d{1,3})$/;
分支结构
/can|candy/
前面满足了,后面就不会实验了。